The present invention relates to a method for anonymously reading database records, wherein each record has different access control permissions.
When controlling access to a sensitive resource, it is clear that the applicable access control policies can already reveal too much information about the resource. An example is a medical database containing patient records, where the access control list (ACL) of each record lists the names of the treating doctors. The fact that a patient's record has certain specialists in its ACL leaks information about the patient's disease. Many patients want to hide the fact that they are being treated by a plastic surgeon or a psychiatrist. Also, doctors treating a celebrity want to remain anonymous to avoid being approached by the press. As another example, in a multi-user file system, it can be desirable to hide the owner of a file or the groups that have access to it to prevent social engineering attacks, coercion, and bribery. In a military setting, knowing which files are classified “top secret”, or even just the percentage of “top secret” files in the system, can help an attacker to focus his attack.
But confidentiality of the stored data is not the only security concern. Privacy-aware users accessing the database can be worried about malicious database servers prying information from the query traffic. For example, the frequency that a patient's record is accessed gives a good idea of the seriousness of his condition, while the identity of the doctors that access it most frequently can be an indication of the nature of the disorder. Users can query the database anonymously, i.e., hiding their identity, roles, permissions, etc. from the database server, as well as hiding the index of the queried record. At the same time, the database server can be confident that only permitted users have access to the data, and that they cannot find out whom else has access to the data.
Oblivious transfer (OT) protocols in their basic form offer users access to a database without the server learning the contents of the query, but place no restrictions on who can access which records. In the paper by J. Herranz, “Restricted adaptive oblivious transfer”, Cryptology ePrint Archive, Report 2008/182, 2008, access control restrictions were added to records the first time, but users have to authenticate openly (i.e., non-anonymously) to the server. Later, Coull et al. (“Controlling access to an oblivious database using stateful anonymous credentials”, in PKC 2009, LNCS, vol. 5443, 501-520, Springer, 2009) and Camenisch et al. (“Oblivious transfer with access control”, in ACM CCS 09, 131-140, ACM Press, 2009) proposed OT protocols with anonymous access control. In all of these works, however, the access control policies are assumed to be publicly available to all users, and the server notices when a user attempts to access a record for which she does not have the right credentials.
There is a line of work devoted to access control with hidden policies and hidden credentials, but none of them consider oblivious access to data, i.e., the server learns which resource is being accessed. In trust negotiation systems two parties establish trust through iterative disclosure of and requests for credentials. Hidden credentials systems are designed to protect sensitive credentials and policies. However, full protection of policies is not provided in the sense that the user learns (partial) information about the policy if her credentials satisfy it. The protocol of Frikken et al. (“Attribute-based access control with hidden policies and hidden credentials”, IEEE Trans. Computers, 55(10):1259-1270, 2006) does provide full protection, but for arbitrary policies it requires communication exponential in the size of the policies.
One can always implement a protocol with all desired properties by evaluating an especially designed logical circuit using generic two-party computation techniques (A.C. Yao, “Protocols for secure computations”, in 23rd FOCS, 160-164, IEEE Computer Society Press, 1982), but the cost of this approach can be prohibitive. In particular, the computation and communication cost of each record transfer can be linear in the number of records in the database N, whereas the efficiency of our transfer protocol is independent of N.
It is therefore desirable to combine the advantages of an oblivious access control protocol with hidden ACLs. But for example the protocol of Camenisch et al. relies heavily on zero-knowledge proofs of knowledge that a user's credentials satisfy the applicable ACL. Such approaches no longer work for hidden ACLs because the user does not know the statement that has to be proven. In fact, the user does not even know whether the statement is true at all.